<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>

  <script>
    /*
      插入排序2
        + 原始数组开始遍历
    */

    // 准备原始数组
    var arr = [ 4, 7, 2, 8, 3, 6, 9, 1, 5 ]

    // 插入排序
    for (var i = 1; i < arr.length; i++) {
      // 1. 把本次要操作的数字记录下来
      var tmp = arr[i]

      // 2. 向前循环开始比较
      // 开始: 当前索引 - 1, i - 1
      // 步长: -1
      // 条件: 什么时候停 ? 前一个比我小. 什么时候不停 ? 前一个比我大
      // 如果前一个比我大, 那么直接让前一个替换我现在的位置
      var j = i - 1
      while (arr[j] > tmp) {
        arr[j + 1] = arr[j]
        j--
      }

      // 3. 循环结束, 说明 arr[j] > tmp === false
      // 说明 arr[j] < tmp
      // 说明 j 位置的数据比 tmp 小, 应该把 tmp 赋值给 [j + 1] 位置的数据
      arr[j + 1] = tmp
    }

    console.log(arr)


  </script>
</body>
</html>
